백준 1753번 - 최단경로

문제 링크

조건

V=20000
E=300000

풀이과정

다익스트라

실패 시간초과

vv, e = map(int, input().split())

k = int(input())

INF = int(1e9)
distance = [INF] * (vv + 1)
visited = [False] * (vv + 1)
graph = {}

for _ in range(e):
    u, v, w = list(map(int, input().split()))
    if u not in graph:
        graph[u] = {v: w}
        continue
    if v not in graph[u]:
        graph[u][v] = w
        continue
    graph[u][v] = min(graph[u][v], w)


def min_distance_node():
    min_distance = INF
    min_idx = INF
    for idx in range(1, vv + 1):
        if visited[idx] == False and distance[idx] < min_distance:
            min_distance = distance[idx]
            min_idx = idx
    return min_idx


def dijkstra(start):
    distance[start] = 0
    next = start
    while next != INF:
        visited[next] = True
        if next in graph:
            for node, dis in graph[next].items():
                distance[node] = min(distance[node], distance[next] + dis)
        next = min_distance_node()


dijkstra(k)
for i in distance[1:]:
    if i == INF:
        print("INF")
        continue
    print(i)

우선순위 큐 다익스트라

성공 700ms

그렇다면 우선순위 큐로 개선된 다익스트라로 풀어보자
개선된 다익스트라의 시간복잡도는 O((V+E)$logV$) 이므로
$300000\ast 4=1200000$ 으로 줄어서 시간 초과가 발생하지 않는다!

import heapq
import sys

vv, e = map(int, input().split())

k = int(input())

INF = int(1e9)
distance = [INF] * (vv + 1)
visited = [False] * (vv + 1)
graph = {}

for _ in range(e):
    u, v, w = list(map(int, sys.stdin.readline().split()))
    if u not in graph:
        graph[u] = {v: w}
        continue
    if v not in graph[u]:
        graph[u][v] = w
        continue
    graph[u][v] = min(graph[u][v], w)


def dijkstra(start):
    distance[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    while len(heap):
        dis, node = heapq.heappop(heap)
        if node not in graph:
            continue
        for neigh_idx, neigh_dis in graph[node].items():
            if distance[neigh_idx] > dis + neigh_dis:
                distance[neigh_idx] = dis + neigh_dis
                heapq.heappush(heap, (distance[neigh_idx], neigh_idx))


dijkstra(k)
for i in distance[1:]:
    if i == INF:
        print("INF")
        continue
    print(i)

관련글

• 최단경로